import java.util.ArrayList;

/**
 * Created with IntelliJ IDEA.
 * Description: 牛客网: BM60 括号生成
 * <a href="https://www.nowcoder.com/practice/c9addb265cdf4cdd92c092c655d164ca?tpId=295&tqId=725&ru=/exam/company&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Fcompany">...</a>
 * User: DELL
 * Date: 2023-06-02
 * Time: 23:53
 */
public class Solution {
    /**
     * 解题思路: (深度优先遍历)
     * 本题只要把握住右括号的数量不能多于左括号就行,基于这一点展开深度优先算法就很简单.
     * @param n int整型
     * @return string字符串ArrayList
     */
    public ArrayList<String> generateParenthesis (int n) {
        ArrayList<String> res = new ArrayList<>();
        StringBuffer temp = new StringBuffer();
        dfs(res,temp,0,0,n);
        return res;
    }

    /**
     * 深度优先遍历
     * @param res       存放结果
     * @param temp      临时存放括号
     * @param leftNum   已使用的左括号的数量
     * @param rightNum  已使用的右括号的数量
     * @param n         左右括号的个数
     */
    private void dfs(ArrayList<String> res, StringBuffer temp, int leftNum, int rightNum, int n) {
        if (leftNum == n && rightNum == n) {
            res.add(temp.toString());
            return;
        }
        //左括号不够先添加左括号
        if (leftNum != n) {
            temp.append('(');
            dfs(res,temp,leftNum+1,rightNum,n);
            temp.delete(leftNum+rightNum,leftNum+rightNum+1);
        }
        //左括号数量比右括号数量多,就可以添加右括号
        if (leftNum > rightNum) {
            temp.append(')');
            dfs(res,temp,leftNum,rightNum+1,n);
            temp.delete(leftNum+rightNum,leftNum+rightNum+1);
        }
    }
}